#include <iostream>
#include <string>
#include <stack>
#include <sstream>
#include <vector>
#include <cmath>
#include <stack>
using namespace std;
char test;

class trueTable{
    vector<string> logicElement;    //组成元素
    vector<vector<int>> table;      //真值表
    int basicNum;
    int column;

    public:
    bool cmp(trueTable T){
        int k1=this->logicElement.size(),k2=T.logicElement.size();
        if(T.column!=this->column) return 0;
        int n1=this->basicNum,n2=T.basicNum;
        if(n1!=n2) return 0;  
        for(int i=0;i<n1;i++){  //基本元素不同
            if(this->logicElement[i]!=T.logicElement[i]){
                return 0;
            }
        }

        for(int i=0;i<column;i++){
            if(this->table[i][k1-1]!=T.table[i][k2-1]) return 0;
        }
        return 1;

    }
    void cal_not(string s){     //!
        logicElement.push_back("!"+s);  //推入新元素名称
        int n=search(s);
        for(int i=0;i<column;i++){  //做非运算
            table[i].push_back(1-table[i][n]);
        }
        return;
    }

    int And(int a,int b){   //与运算
        if(a==1 && b==1) return 1;
        return 0;
    }
    void cal_and(string s1,string s2){  //&
        logicElement.push_back(s1+"&"+s2);
        int n1=search(s1),n2=search(s2);
        for(int i=0;i<column;i++){
            table[i].push_back(And(table[i][n1],table[i][n2]));
        }
        return ;
    }

    int Or(int a,int b){
        return !(a==0 && b==0); 
    }
    void cal_or(string s1,string s2){  //|
        logicElement.push_back(s1+"|"+s2);
        int n1=search(s1),n2=search(s2);
        for(int i=0;i<column;i++){
            table[i].push_back(Or(table[i][n1],table[i][n2]));
        }
        return ;
    }

    int If(int a,int b){
        return !(a==0 && b==1);
    }
    void cal_if(string s1,string s2){   //->
        logicElement.push_back(s1+"->"+s2);
        int n1=search(s1),n2=search(s2);
        for(int i=0;i<column;i++){
            table[i].push_back(If(table[i][n1],table[i][n2]));
        }
        return ;
    }

    bool add(string s){ //添加初始元素
        if(-1==search(s)){
            logicElement.push_back(s);
            return 1;
        }
        return 0;
    }
    int search(string s){   //按名称查找下标,注意排除外括号
        int k=logicElement.size();
        if(s[0]=='('){
            bool f=1;
            for(int i=1;i<k && f;i++){
                if(s[i]==')' && i!=k-1) f=0;  //说明不是外括号
            }
            if(f){    //去掉外括号
                s=s.substr(1,s.size()-2);
            } 
        }
        for(int i=0;i<k;i++){
            if(s==logicElement[i]) return i;
        }
        return -1;
    }

    void reOrder(){     //基本元素重排序
        int k=logicElement.size();
        for(int i=0;i<k-1;i++){
            for(int j=k-1;j>i;j--){
                if(logicElement[j]<logicElement[j-1]){      //冒泡排成字符表序
                    string tmp=logicElement[j];
                    logicElement[j]=logicElement[j-1];
                    logicElement[j-1]=tmp;
                }
            }
        }
        return ;
    }

    void initialLise(){
        int k=logicElement.size();
        this->basicNum=k;
        this->column=1;
        if(k==0) this->column=0;
        else {
            for(int i=0;i<k;i++){
                this->column*=2;
            }
        }
        vector<int> v;
        initialLise_r(v,k);     //初始化基本元素的真值表
        reOrder();
        return ;
    }
    void initialLise_r(vector<int> v,int k){
        vector<int> v1=v;
        if(k==1){
            for(int i=0;i<2;i++){
                v1.push_back(i);
                this->table.push_back(v1);
                v1=v;
            }
            return ;
        } else {
            for(int i=0;i<2;i++){
                v1.push_back(i);
                initialLise_r(v1,k-1);
                v1=v;
            }
            return ;
        }
    }
    void printTable(){
        int k=logicElement.size();
        for(int i=0;i<this->column+1;i++){
            for(int j=0;j<k;j++){
                if(!i){
                    cout<<logicElement[j]<<" ";
                }
                else{
                    cout<<table[i-1][j]<<" ";
                    int len=logicElement[j].size()-1;
                    if(len)
                        for(int p=0;p<len;p++){
                            cout<<" ";
                        }
                }
            }
            cout<<endl;
        }
    }
};

const int opt[7][7]={0,2,2,2,2,2,2,1,1,1,2,2,1,1,1,2,1,2,2,1,1,1,1,1,1,2,1,1,3,2,2,2,2,0,2,1,1,1,1,3,1,1,1,2,2,2,2,1,1};     //运算符优先级,1是大于，0是等于，2是小于,3是error

int searchFor(string s){    //返回符号的数组下标
    if(s=="#") return 0;
    if(s=="&") return 1;
    if(s=="|") return 2;
    if(s=="!") return 3;
    if(s=="(") return 4;
    if(s==")") return 5;
    if(s=="->" || s=="-") return 6;
    return -1;
}

void logicConstruct(string s,trueTable &T){
    stack<string> ele;
    stack<string> op;
    op.push("#");
    s=s+"#";
    int k=s.length();

    for(int i=0;i<k;i++){   //初始化
        switch(s[i]){
            case '#':
            case '&':
            case '|':
            case '!':
            case '-':
            case '>':
            case '(':
            case ')':
            case ' ':break;
            default:{   //添入基本元素
                T.add(s.substr(i,1));
            }
        }
    }
    T.initialLise();

    for(int i=0;i<k;i++){
        if(s[i]==' ') continue;
    
        string tmp=op.top();
        if(searchFor(s.substr(i,1))==-1){
            ele.push(s.substr(i,1));
        } else 
            switch(tmp[0]){
                case '#':{
                    switch(opt[0][searchFor(s.substr(i,1))]){
                        case 0:{
                            op.pop();
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                };
                case '&':{
                    switch(opt[1][searchFor(s.substr(i,1))]){
                        case 1:{
                            op.pop();
                            string str[2];
                            str[1]=ele.top();
                            ele.pop();
                            str[0]=ele.top();
                            ele.pop();
                            T.cal_and(str[0],str[1]);
                            ele.push(str[0]+"&"+str[1]);
                            i=i-1;
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                };
                case '|':{
                    switch(opt[2][searchFor(s.substr(i,1))]){
                        case 1:{
                            op.pop();
                            string str[2];
                            str[1]=ele.top();
                            ele.pop();
                            str[0]=ele.top();
                            ele.pop();
                            T.cal_or(str[0],str[1]);
                            ele.push(str[0]+"|"+str[1]);
                            i=i-1;
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                }
                case '!':{
                    switch(opt[3][searchFor(s.substr(i,1))]){
                        case 1:{
                            op.pop();
                            string str;
                            str=ele.top();
                            ele.pop();
                            T.cal_not(str);
                            ele.push("!"+str);
                            i=i-1;
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                }
                case '-':{
                    switch(opt[6][searchFor(s.substr(i,1))]){
                        case 1:{
                            op.pop();
                            string str[2];
                            str[1]=ele.top();
                            ele.pop();
                            str[0]=ele.top();
                            ele.pop();
                            T.cal_if(str[0],str[1]);
                            ele.push(str[0]+"->"+str[1]);
                            i=i-1;
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                }
                case '(':{
                    switch(opt[4][searchFor(s.substr(i,1))]){
                        case 0:{
                            op.pop();
                            string s=ele.top();
                            ele.pop();
                            ele.push("("+s+")");
                            break;
                        };
                        case 2:{
                            if(s[i]=='-'){
                                op.push(s.substr(i,2));
                                i+=1;
                            } else {
                                op.push(s.substr(i,1));
                            }
                        }
                    }
                    break;
                }
                case ')':{

                    break;
                }
                case ' ':break;
            }
    }
    return;
}

int main(){
    trueTable tableP,tableQ;
    string s;
    cout<<"请输入表达式p:";
    getline(cin,s);
    logicConstruct(s,tableP);
    tableP.printTable();
    cout<<"请输入表达式q:";
    getline(cin,s);
    logicConstruct(s,tableQ);
    tableQ.printTable();
    if(tableP.cmp(tableQ)) cout<<"逻辑等价";
    else cout<<"逻辑不等价";
    return 0;
}